package class09;

import class06.LinkedListMid;
import sun.reflect.generics.tree.Tree;

import java.util.LinkedList;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class IsCBT {

    public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int v){
            val = v;
        }
    }

    public static boolean isCompleteTree(TreeNode head){
        if (head == null)
            return true;
        LinkedList<TreeNode> queue = new LinkedList<>();
        boolean leaf = false;
        TreeNode l =null;
        TreeNode r = null;
        queue.add(head);
        while (!queue.isEmpty()){
            head = queue.poll();
            l = head.left;
            r = head.right;
            if (
                    (leaf &&(l!=null || r!=null)) ||
                            (l == null && r !=null)
            ){
                return false;
            }
            if (l!=null){
                queue.add(l);
            }
            if (r!=null){
                queue.add(r);
            }
            if (l==null || r ==null){
                leaf = true;
            }
        }
        return true;
    }

    public static class Info{
        public boolean isFull;
        public boolean isCBT;
        public int height;

        public Info(boolean full,boolean cbt,int h){
            isFull = full;
            isCBT = cbt;
            height = h;
        }
    }


    public static boolean isCompleteTree2(TreeNode head){
        return process(head).isCBT;
    }


    public static Info process(TreeNode x){
        if (x == null){
            return  new Info(true,true,0);
        }

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int height = Math.max(leftInfo.height,rightInfo.height)+1;

        boolean isfull = leftInfo.isFull && rightInfo.isFull &&
                leftInfo.height==rightInfo.height;

        boolean isCBT = false;

        if (leftInfo.isFull &&
                rightInfo.isFull &&
                leftInfo.height == rightInfo.height
        ){
            isCBT = true;
        }else {
            if (leftInfo.isCBT && rightInfo.isCBT){
                if (leftInfo.isCBT &&
                        rightInfo.isFull &&
                        leftInfo.height == rightInfo.height+1
                )
                    isCBT = true;
                if (
                        leftInfo.isFull &&
                                rightInfo.isFull &&
                                leftInfo.height == rightInfo.height+1
                )
                    isCBT = true;
                if (
                        leftInfo.isFull &&
                                rightInfo.isCBT &&
                                leftInfo.height == rightInfo.height
                )
                    isCBT = true;
            }
        }
        return new Info(isfull,isCBT,height);
    }

    public static TreeNode generateRandomBST(int maxLevel,int maxValue){
        return generate(1,maxLevel,maxValue);
    }

    public static TreeNode generate(int level,int maxLevel,int maxValue){
        if (level > maxLevel ||Math.random()>0.5)
            return null;
        TreeNode head = new TreeNode((int)(Math.random()*maxValue));
        head.left = generate(level+1,maxLevel,maxValue);
        head.right = generate(level+1,maxLevel,maxValue);
        return head;
    }

    public static void main(String[] args) {
        int maxLevel = 5;
        int maxValue = 100;
        int testTime = 1000000;
        for(int i=0;i<testTime;i++){
            TreeNode head = generateRandomBST(maxLevel,maxValue);
            if (isCompleteTree(head)!=isCompleteTree2(head))
                System.out.println("Oops!");
        }
        System.out.println("finish!");
    }

}
